package com.justnow.offer;

public class Solution42 {
    /**
     * 方法一，超级简单的动态规划方法，对原有数组进行修改
     *
     * @param nums
     * @return
     */
    public static int maxSubArray1(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            //nums[i]为以该元素结尾的最大连续数组和，通过判断原始数组元素是否为负数来实现。
            res = Math.max(res, nums[i]);
        }
        return res;
    }

    /**
     * 方法二，不修改原有的数组
     *
     * (1)状态定义： 设动态规划列表dp，dp[i]代表以元素nums[i]为结尾的连续子数组最大和
     *
     * @param nums
     * @return
     */
    public static int maxSubArray2(int[] nums) {

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {

            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);

            max = Math.max(dp[i], max);
        }

        return max;
    }

    /**
     * 题解在算法总结上面
     * @param nums
     * @return
     */
    public static int maxSubArray3(int[] nums) {
        int[] dp = new int[nums.length + 1];
        int max = nums[0];//防止只要一个因素
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i-1] < 0)
                dp[i] = nums[i];
            else
                dp[i] = dp[i - 1] + nums[i];
            max = Math.max(dp[i], max);
        }
        return max;
    }
    public static void main(String[] args) {
        int i = Solution42.maxSubArray1(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
        int i2 = Solution42.maxSubArray2(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
        int i3 = Solution42.maxSubArray3(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
        System.out.println(i + " : " + i2 + " : " + i3);
    }
}
